1287C - Garland - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define endl "\n"
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<< #x <<" : "<<(x)<<endl;
#define dbgv(v) cout<< #v <<" : ";for(auto &i:v) cout<<(i)<<" ";cout<<endl;
void solve()
// int solve()
{
    int n;cin>>n;
    vector<int> v(n);
    vector<int> nd(n+1,1);
    for(int &i:v) {cin>>i; if(i==0) i=-1; else {nd[i] = 0;i%=2;}}
    if(n == 1){
        cout<<0<<endl;return;
    }
    if(count(all(v),-1) == n) {
        cout<<1<<endl;return;
    }
    int l = -1;
    vector<vector<int>> x(2);
    vector<vector<int>> b(2);
    int ans = 0;
    for(int i=0;i<n;i++)
    {
        if(v[i] !=-1) {

            if(l == (!v[i])) ans++;
            l = v[i];
        }
        else
        {
            int c = 0;
            while(v[i]==-1) {c++;i++;}
            if(i == n)
            {
                b[l].push_back(c);
            }
            else if(l == -1){
                b[v[i]].push_back(c);
            }
            else if(l == v[i])
                x[l].push_back(c);
            i--;
        }
    }
    int o=0,z=0;
    for(int i=1;i<=n;i++)
    {
        if(i%2) o+=(nd[i]);
        else z+=(nd[i]);
    }

    sort(all(x[0]));
    sort(all(b[0]));
    sort(all(x[1]));
    sort(all(b[1]));
    int sm = 0;
    for(int i=0;i<x[0].size();i++)
    {
        if(sm + x[0][i] > z) {
            ans += 2*(x[0].size() - i);
            break;
        }
        sm+=x[0][i];
    }
    for(int i=0;i<b[0].size();i++)
    {
        if(sm + b[0][i] > z) {
            ans += (b[0].size() - i);
            break;
        }
        sm+=b[0][i];
    }
    sm = 0;
    for(int i=0;i<x[1].size();i++)
    {
        if(sm + x[1][i] > o) {
            ans += 2*(x[1].size() - i);
            break;
        }
        sm+=x[1][i];
    }
    for(int i=0;i<b[1].size();i++)
    {
        if(sm + b[1][i] > o) {
            ans += (b[1].size() - i);
            break;
        }
        sm+=b[1][i];
    }
    cout<<ans<<endl;
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin>>t;
    while(t--)
    {
        solve();
        // cout<<solve()<<endl;
    }
    return 0;
}